package _interview100;

import java.util.*;

/**
 * 295. 数据流的中位数
 */
public class No295 {
    private final Queue<Integer> minHeap;
    private final Queue<Integer> maxHeap;

    public No295() {
        minHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (minHeap.isEmpty() || num <= minHeap.peek()) {
            minHeap.offer(num);
            if (minHeap.size() > maxHeap.size() + 1) {
                maxHeap.offer(minHeap.poll());
            }
        } else {
            maxHeap.offer(num);
            if (maxHeap.size() > minHeap.size()) {
                minHeap.offer(maxHeap.poll());
            }
        }
    }

    public double findMedian() {
        return minHeap.size() > maxHeap.size() ? minHeap.peek() : (minHeap.peek() + maxHeap.peek()) / 2.0;
    }
}
